Infinite family of transmission irregular trees of even order

Distance between two vertices is the number of edges in a shortest path connecting them in a connected graph $G$. The transmission of a vertex $v$ is the sum of distances from $v$ to all the other vertices of $G$. If transmissions of all vertices are mutually distinct, then $G$ is a transmission irregular graph. It is known that almost no graphs are transmission irregular. Infinite families of transmission irregular trees of odd order were presented in Alizadeh and Klav?ar (2018). The following problem was posed in Alizadeh and Klav?ar (2018): do there exist infinite families of transmission irregular trees of even order? In this article, such a family is constructed.     

On a problem of Neumann

A conjecture widely attributed to Neumann is that all finite non-desarguesian projective planes contain a Fano subplane. In this note, we show that any finite projective plane of even order which admits an orthogonal polarity contains many Fano subplanes. The number of planes of order less than $n$ previously known to contain a Fano subplane was $O(logn)$, whereas the number of planes of order less than $n$ that our theorem applies to is not bounded above by any polynomial in $n$.     

On a family of highly regular graphs by Brouwer,Ivanov, and Klin

Highly regular graphs for which not all regularities are explainable by symmetries are fascinating creatures. Some of them like, e.g., the line graph of W. Kantor’s non-classical $GQ(5^2,5)$, are stumbling stones for existing implementations of graph isomorphism tests. They appear to be extremely rare and even once constructed it is difficult to prove their high regularity. Yet some of them, like the McLaughlin graph on 275 vertices and Ivanov’s graph on 256 vertices are of profound beauty. This alone makes it an attractive goal to strive for their complete classification or, failing this, at least to get a deep understanding of them. Recently, one of the authors discovered new methods for proving high regularity of graphs. Using these techniques, in this paper we study a classical family of strongly regular graphs, originally discovered by A.E. Brouwer, A.V. Ivanov, and M.H. Klin in the late 80s. We analyse their symmetries and show that they are $(3,5)$-regular but not 2-homogeneous. Thus we promote these graphs to the distinguished club of highly regular graphs with few symmetries.     

Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable

Wang and Lih (2002) conjectured that every planar graph without adjacent triangles is 4-choosable. In this paper, we prove that every planar graph without any 4-cycle adjacent to two triangles is DP-4-colorable, which improves the results of Lam et al. (1999), Cheng et al. (2016) and Kim and Yu [ arXiv:1709.09809v1].     

The maximum multiplicity of the largest k-th eigenvalue in a matrix whose graph is acyclic or unicyclic

Given a graph $G$ we are interested in studying the symmetric matrices associated to $G$ with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees.     

Ends,tangles and critical vertex sets

We show that an arbitrary infinite graph G can be compactified by its ends plus its critical vertex sets, where a finite set X of vertices of an infinite graph is critical if its deletion leaves some infinitely many components each with neighbourhood precisely equal to X. We further provide a concrete separation system whose ?₀‐tangles are precisely the ends plus critical vertex sets. Our tangle compactification is a quotient of Diestel's (denoted by ), and both use tangles to compactify a graph in much the same way as the ends of a locally finite and connected graph compactify it in its Freudenthal compactification. Finally, generalising both Diestel's construction of and our construction of , we show that G can be compactified by every inverse limit of compactifications of the sets of components obtained by deleting a finite set of vertices. Diestel's is the finest such compactification, and our is the coarsest one. Both coincide if and only if all tangles are ends. This answers two questions of Diestel.